package solutions.leetcode.hard;

import solutions.lib.BaseSolution;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/trapping-rain-water-ii/">407. 接雨水 II</a>
 */
public class Solution407 extends BaseSolution {

    public int trapRainWater(int[] height) {
        int[] rst = new int[height.length];
        int max = height[0];
        int p = 1;
        int maxI = 0;
        while (p < height.length) {
            if (height[p] >= max) {
                int m = max;
                max = height[p];
                for (int i = maxI + 1; i < p; i++) {
                    rst[i] = m - height[i];
                }
                maxI = p;
            } else if (height[p] > height[p - 1]) {
                for (int i = p - 1; i >= maxI; i--) {
                    if (height[i] >= height[p]) {
                        break;
                    }
                    rst[i] = height[p] - height[i];
                }
            }
            p++;
        }
        int c = 0;
        for (int v : rst) {
            c += v;
        }
        return c;
    }

    public static void main(String[] args) {
        Solution407 solution = new Solution407();
        System.out.println(solution.trapRainWater(new int[] {
                4,2,0,3,2,5
        }));
    }
}